Thuật toán tìm kiếm nhị phân hoạt động trên các mảng đã được sắp xếp. Thuật toán bắt đầu bằng việc so sánh một phần tử đứng chính giữa mảng với giá trị cần tìm. Nếu bằng nhau, vị trí của nó trong mảng sẽ được trả về. Nếu giá trị cần tìm nhỏ hơn phần tử này, quá trình tìm kiếm tiếp tục ở nửa nhỏ hơn của mảng. Nếu giá trị cần tìm lớn hơn phần tử ở giữa, quá trình tìm kiếm tiếp tục ở nửa lớn hơn của mảng. Bằng cách này, ở mỗi phép lặp thuật toán có thể loại bỏ nửa mảng mà giá trị cần tìm chắc chắn không xuất hiện.[7]

Quy trình

Cho một mảng A {\displaystyle A} có n {\displaystyle n} phần tử với các giá trị hoặc bản ghi A 0 , A 1 , A 2 , … , A n − 1 {\displaystyle A_{0},A_{1},A_{2},\ldots ,A_{n-1}} đã được sắp xếp sao cho A 0 ≤ A 1 ≤ A 2 ≤ ⋯ ≤ A n − 1 {\displaystyle A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}} , và giá trị cần tìm T {\displaystyle T} , chương trình con sau đây sử dụng tìm kiếm nhị phân để tìm chỉ số của T {\displaystyle T} trong A {\displaystyle A} .[7]

1. Gán L {\displaystyle L} với giá trị 0 {\displaystyle 0} và R {\displaystyle R} với giá trị n − 1 {\displaystyle n-1} .
2. Nếu L > R {\displaystyle L>R} , tìm kiếm kết thúc (không thành công).
3. Gán m {\displaystyle m} (vị trí của phần tử đứng giữa) với giá trị floor của L + R 2 {\displaystyle {\frac {L+R}{2}}} , tức là số nguyên lớn nhất nhỏ hơn hoặc bằng L + R 2 {\displaystyle {\frac {L+R}{2}}} .
4. Nếu A m < T {\displaystyle A_{m}<T} , gán L {\displaystyle L} với m + 1 {\displaystyle m+1} và quay lại bước 2.
5. Nếu A m > T {\displaystyle A_{m}>T} , gán R {\displaystyle R} với m − 1 {\displaystyle m-1} và quay lại bước 2.
6. Khi A m = T {\displaystyle A_{m}=T} , quá trình tìm kiếm hoàn tất; trả về m {\displaystyle m} .

Quy trình lặp này dùng hai biến L {\displaystyle L} và R {\displaystyle R} để lưu giới hạn tìm kiếm. Quy trình này có thể diễn giải bằng mã giả như dưới đây, trong đó tên các biến và kiểu giữ nguyên so với như trên, floor là hàm floor, và không_thành_công là một giá trị cụ thể thông báo tìm kiếm thất bại.[8]

function binary_search(A, n, T) is    L:= 0    R:= n − 1    while L ≤ R do        m:= floor((L + R) / 2)        if A[m] < T then            L:= m + 1        else if A[m] > T then            R:= m - 1        else:            return m    return không_thành_công

Ngoài ra, thuật toán có thể lấy giá trị ceiling của L + R 2 {\displaystyle {\frac {L+R}{2}}} . Điều này có thể thay đổi kết quả nếu giá trị cần tìm xuất hiện nhiều hơn một lần trong mảng.

Cách làm khác

Trong quy trình trên, thuật toán kiểm tra phần tử ở giữa ( m {\displaystyle m} ) có bằng giá trị cần tìm ( T {\displaystyle T} ) không ở mỗi phép lặp. Một số cách làm bỏ qua bước này ở mỗi phép lặp. Khi đó thuật toán chỉ kiểm tra điều này khi chỉ còn một phần tử còn lại (khi L = R {\displaystyle L=R} ). Nhờ đó mà vòng lặp so sánh được thực hiện nhanh hơn do mỗi phép lặp đã loại bỏ được một bước so sánh. Tuy nhiên, với cách làm này thì số phép lặp trung bình tăng lên.[9]

Hermann Bottenbruch cho xuất bản cách áp dụng đầu tiên bỏ qua bước kiểm tra này vào năm 1962.[9][10]

1. Gán L {\displaystyle L} với giá trị 0 {\displaystyle 0} và R {\displaystyle R} với giá trị n − 1 {\displaystyle n-1} .
2. Khi L ≠ R {\displaystyle L\neq R} ,
   1. Gán m {\displaystyle m} (vị trí của phần tử đứng giữa) với giá trị ceiling của L + R 2 {\displaystyle {\frac {L+R}{2}}} , tức là số nguyên nhỏ nhất lớn hơn hoặc bằng L + R 2 {\displaystyle {\frac {L+R}{2}}} .
   2. Nếu A m > T {\displaystyle A_{m}>T} , gán R {\displaystyle R} với m − 1 {\displaystyle m-1} .
   3. Trường hợp còn lại, A m ≤ T {\displaystyle A_{m}\leq T} ; gán L {\displaystyle L} với m {\displaystyle m} .
3. Khi L = R {\displaystyle L=R} , quá trình tìm kiếm hoàn tất. Nếu A L = T {\displaystyle A_{L}=T} , trả về L {\displaystyle L} . Nếu không, tìm kiếm thất bại.

Với ceil là hàm ceiling, mã giả cho phiên bản này như sau:

function binary_search_alternative(A, n, T) is    L:= 0    R:= n − 1    while L != R do        m:= ceil((L + R) / 2)        if A[m] > T then            R:= m - 1        else:            L:= m    if A[L] = T then        return L    return không_thành_công    

Phần tử lặp lại

Quy trình trên có thể trả về bất cứ chỉ số nào có giá trị phần tử bằng giá trị cần tìm, kể cả khi trong mảng có các phần tử xuất hiện lặp lại. Ví dụ, với mảng [ 1 , 2 , 3 , 4 , 4 , 5 , 6 , 7 ] {\displaystyle [1,2,3,4,4,5,6,7]} và giá trị cần tìm là 4 {\displaystyle 4} , thuật toán có thể trả về một trong hai kết quả đúng là phần tử thứ 4 (chỉ số là 3) hoặc thứ 5 (chỉ số là 4). Quy trình chuẩn trong trường hợp này sẽ trả về phần tử thứ 4 (chỉ số 3). Thuật toán này không phải lúc nào cũng trả về vị trí đầu tiên xuất hiện giá trị cần tìm (ví dụ với mảng [ 1 , 2 , 4 , 4 , 4 , 5 , 6 , 7 ] {\displaystyle [1,2,4,4,4,5,6,7]} , kết quả trả về vẫn là phần tử thứ 4). Tuy nhiên, có một số trường hợp cần phải tìm phần tử nằm xa nhất về phía bên trái hoặc bên phải mang giá trị cần tìm khi giá trị này xuất hiện lặp lại trong mảng. Trong ví dụ trên, phần tử thứ 4 là phần tử đứng xa nhất về bên trái mang giá trị 4, trong khi phần tử thứ 5 là phần từ đứng xa nhất về bên phải mang giá trị 4. Cách làm thứ hai ở trên sẽ luôn trả về chỉ số của phần tử đứng xa nhất về bên phải nếu tồn tại các phần tử lặp lại.[10]

Quy trình tìm phần tử xa nhất về bên trái

Để tìm phần tử xa nhất về bên trái, ta có thể dùng quy trình sau:[11]

1. Gán L {\displaystyle L} với giá trị 0 {\displaystyle 0} và R {\displaystyle R} với n {\displaystyle n} .
2. Khi L < R {\displaystyle L<R} ,
3. Gán m {\displaystyle m} (vị trí của phần tử đứng giữa) với giá trị floor của L + R 2 {\displaystyle {\frac {L+R}{2}}} , tức là số nguyên lớn nhất nhỏ hơn hoặc bằng L + R 2 {\displaystyle {\frac {L+R}{2}}} .
   1. Nếu A m < T {\displaystyle A_{m}<T} , gán L {\displaystyle L} với m + 1 {\displaystyle m+1} .
   2. Trường hợp còn lại, A m ≥ T {\displaystyle A_{m}\geq T} ; gán R {\displaystyle R} với m {\displaystyle m} .
4. Trả về L {\displaystyle L} .

Nếu L < n {\displaystyle L<n} và A L = T {\displaystyle A_{L}=T} thì A L {\displaystyle A_{L}} là phần tử đứng xa nhất về bên trái có giá trị bằng T {\displaystyle T} . Kể cả khi T {\displaystyle T} không nằm trong mảng, L {\displaystyle L} là hạng của T {\displaystyle T} trong mảng, hay số phần tử trong mảng nhỏ hơn T {\displaystyle T} .

Với floor là hàm floor, mã giả cho phiên bản này như sau:

function binary_search_leftmost(A, n, T):    L:= 0    R:= n    while L < R:        m:= floor((L + R) / 2)        if A[m] < T:            L:= m + 1        else:            R:= m    return L

Quy trình tìm phần tử xa nhất về bên phải

Để tìm phần tử xa nhất về bên phải, ta có thể dùng quy trình sau:[11]

1. Gán L {\displaystyle L} với giá trị 0 {\displaystyle 0} và R {\displaystyle R} với n {\displaystyle n} .
2. Khi L < R {\displaystyle L<R} ,
3. Gán m {\displaystyle m} (vị trí của phần tử đứng giữa) với giá trị floor của L + R 2 {\displaystyle {\frac {L+R}{2}}} , tức là số nguyên lớn nhất nhỏ hơn hoặc bằng L + R 2 {\displaystyle {\frac {L+R}{2}}} .
   1. Nếu A m > T {\displaystyle A_{m}>T} , gán R {\displaystyle R} với m {\displaystyle m} .
   2. Trường hợp còn lại, A m ≤ T {\displaystyle A_{m}\leq T} ; gán L {\displaystyle L} với m + 1 {\displaystyle m+1} .
4. Trả về R − 1 {\displaystyle R-1} .

Nếu L > 0 {\displaystyle L>0} và A L − 1 = T {\displaystyle A_{L-1}=T} , thì A L − 1 {\displaystyle A_{L-1}} là phần tử đứng xa nhất về phía bên phải có giá trị bằng T {\displaystyle T} . Kể cả khi T {\displaystyle T} không có trong mảng, n − L {\displaystyle n-L} sẽ là số phần tử trong mảng lớn hơn T {\displaystyle T} .

Với floor là hàm floor, mã giả cho phiên bản này như sau:

function binary_search_rightmost(A, n, T):    L:= 0    R:= n    while L < R:        m:= floor((L + R) / 2)        if A[m] > T:            R:= m        else:            L:= m + 1    return R - 1